{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 维护最大堆的算法，令下边为i的根节点子树重新遵循最大堆的性质",
   "id": "6d3399779ec6e76a"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-05T07:32:40.022128Z",
     "start_time": "2024-05-05T07:32:40.014936Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import typing\n",
    "\n",
    "\n",
    "def MaxHeapify(arr: list, i: int, heapSize: int) -> None:\n",
    "    l = 2 * i + 1\n",
    "    r = 2 * i + 2\n",
    "    length = heapSize\n",
    "    maxIndex = i\n",
    "    if l < length and arr[l] > arr[i]:\n",
    "        maxIndex = l\n",
    "    if r < length and arr[r] > arr[maxIndex]:\n",
    "        maxIndex = r\n",
    "    if maxIndex != i:\n",
    "        arr[i], arr[maxIndex] = arr[maxIndex], arr[i]\n",
    "        MaxHeapify(arr, maxIndex, heapSize)\n",
    "\n",
    "\n",
    "def MinHeapify(arr: list, i: int, heapSize: int) -> None:\n",
    "    l = 2 * i + 1\n",
    "    r = 2 * i + 2\n",
    "    length = heapSize\n",
    "    minIndex = i\n",
    "    if l < length and arr[l] < arr[i]:\n",
    "        minIndex = l\n",
    "    if r < length and arr[r] < arr[minIndex]:\n",
    "        minIndex = r\n",
    "    if minIndex != i:\n",
    "        arr[i], arr[minIndex] = arr[minIndex], arr[i]\n",
    "        MaxHeapify(arr, minIndex, heapSize)\n"
   ],
   "id": "a9383db2c7c1fed2",
   "outputs": [],
   "execution_count": 14
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(100), 100)\n",
    "print(arr)\n",
    "MaxHeapify(arr, 0,len(arr))\n",
    "print(arr)"
   ],
   "id": "2f918954e45888d5"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 建堆，对堆中可能有孩子的结点自底向上调用调整堆的函数",
   "id": "32ce21dcbd6601c2"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-05T07:32:40.051341Z",
     "start_time": "2024-05-05T07:32:40.046419Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def BuildMaxHeap(arr: list):\n",
    "    for i in range(len(arr) // 2, -1, -1):\n",
    "        MaxHeapify(arr, i, len(arr))"
   ],
   "id": "cef0542b4761b286",
   "outputs": [],
   "execution_count": 15
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 堆排序算法",
   "id": "433313ac450ac5d"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-05T07:36:42.386725Z",
     "start_time": "2024-05-05T07:36:42.381012Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def HeapSort(arr: list) -> None:\n",
    "    BuildMaxHeap(arr)\n",
    "    heapSize = len(arr)\n",
    "    for i in range(len(arr) - 1, 0, -1):\n",
    "        arr[0], arr[i] = arr[i], arr[0]\n",
    "        heapSize -= 1\n",
    "        MaxHeapify(arr, 0, heapSize)"
   ],
   "id": "1d060e45d654f553",
   "outputs": [],
   "execution_count": 22
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-05T07:36:43.223243Z",
     "start_time": "2024-05-05T07:36:43.217648Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(100), 100)\n",
    "print(arr)\n",
    "HeapSort(arr)\n",
    "print(arr)"
   ],
   "id": "f78f33d73c8c4968",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[43, 37, 74, 80, 97, 86, 2, 8, 48, 17, 6, 20, 33, 51, 18, 26, 45, 64, 14, 7, 41, 15, 25, 12, 11, 81, 19, 29, 72, 22, 10, 13, 24, 55, 34, 91, 90, 63, 87, 28, 65, 3, 71, 62, 75, 32, 60, 39, 70, 49, 92, 68, 94, 83, 9, 52, 67, 4, 66, 69, 73, 36, 82, 58, 79, 99, 30, 59, 95, 42, 35, 40, 27, 61, 5, 78, 16, 84, 57, 76, 38, 50, 93, 31, 98, 44, 96, 77, 47, 23, 53, 0, 89, 1, 85, 21, 54, 56, 46, 88]\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]\n"
     ]
    }
   ],
   "execution_count": 23
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 优先队列\n",
    "- INSERT(S,x): 把元素x插入到集合S中。\n",
    "- MAXIMUM(S): 返回S中具有最大关键字的元素。\n",
    "- EXTRACT_MAX(S): 去掉并返回S中具有最大关键字的元素\n",
    "- INCREASE_KEY(S,x,k): 将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字值。\n",
    "\n",
    "可根据修改compare函数达成输出最小 or 最大"
   ],
   "id": "f790d583f7c316ff"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-05T13:58:17.829559Z",
     "start_time": "2024-05-05T13:58:17.817660Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from typing import List, TypeVar\n",
    "\n",
    "T = TypeVar('T')\n",
    "\n",
    "\n",
    "class PriorityQueue:\n",
    "    def __init__(self, priority: bool = True):\n",
    "        self.heap: List[T] = []\n",
    "        self.priority = priority\n",
    "        self.heapSize = 0\n",
    "\n",
    "    def Insert(self, item: T) -> None:\n",
    "        self.heap.append(item)\n",
    "        self.heapSize += 1\n",
    "        if not self.Empty():\n",
    "            self.__Add_Heapify(self.heapSize - 1)\n",
    "\n",
    "    @property\n",
    "    def Peek(self) -> T | None:\n",
    "        if not self.Empty():\n",
    "            return self.heap[0]\n",
    "        return None\n",
    "\n",
    "    def Extract(self) -> T | None:\n",
    "        if self.Empty():\n",
    "            return None\n",
    "        self.heap[0], self.heap[self.heapSize - 1] = self.heap[self.heapSize - 1], self.heap[0]\n",
    "        self.heapSize -= 1\n",
    "        self.__Extract_Heapify(0)\n",
    "        return self.heap.pop()\n",
    "\n",
    "    def IncreaseKey(self, x: T, k: T) -> None:\n",
    "        \"\"\"\n",
    "        为元素x添加k值\n",
    "        当修改x元素的值之后，尝试向上向下调整\n",
    "        :param x: 指定的元素\n",
    "        :param k: 为指定元素添加的值\n",
    "        :return: \n",
    "        \"\"\"\n",
    "        index = self.heap.index(x)\n",
    "        self.heap[index] += k\n",
    "        self.__Extract_Heapify(index)\n",
    "        self.__Add_Heapify(index)\n",
    "\n",
    "    def Empty(self) -> bool:\n",
    "        return self.heapSize == 0\n",
    "\n",
    "    def __compare(self, item1: T, item2: T) -> int:\n",
    "        \"\"\"\n",
    "        根据priority定义的比较器：\n",
    "            priority为True时，默认为最大优先队列，较大的元素在上边\n",
    "            priority为False时，默认为最小优先队列，较小的元素在上边\n",
    "        调用T类的比较函数\n",
    "        :param item1: 元素1\n",
    "        :param item2: 元素2\n",
    "        \"\"\"\n",
    "        return item1 - item2 if self.priority else item2 - item1\n",
    "\n",
    "    def __Extract_Heapify(self, i: int) -> None:\n",
    "        \"\"\"\n",
    "        从i位置向下调整堆\n",
    "        :param i: 要调整的位置\n",
    "        \"\"\"\n",
    "        l = 2 * i + 1\n",
    "        r = 2 * i + 2\n",
    "        tar = i\n",
    "        if l < self.heapSize and self.__compare(self.heap[i], self.heap[l]) < 0:\n",
    "            tar = l\n",
    "        if r < self.heapSize and self.__compare(self.heap[tar], self.heap[r]) < 0:\n",
    "            tar = r\n",
    "        if tar != i:\n",
    "            self.heap[i], self.heap[tar] = self.heap[tar], self.heap[i]\n",
    "            self.__Extract_Heapify(tar)\n",
    "\n",
    "    def __Add_Heapify(self, i: int) -> None:\n",
    "        \"\"\"\n",
    "        从i位置向上调整堆\n",
    "        :param i: 要调整的位置\n",
    "        \"\"\"\n",
    "        par = (i - 1) // 2\n",
    "        if i > 0 and self.__compare(self.heap[i], self.heap[par]) > 0:\n",
    "            self.heap[par], self.heap[i] = self.heap[i], self.heap[par]\n",
    "            self.__Add_Heapify(par)"
   ],
   "id": "1dcf86dc8dea0419",
   "outputs": [],
   "execution_count": 187
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(20), 20)\n",
    "# print(arr)\n",
    "queue = PriorityQueue(True)\n",
    "[queue.Insert(item) for item in arr]\n",
    "print([queue.Extract() for _ in range(20)])"
   ],
   "id": "9f763afe2eaf836e"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "#### 在一个 mXn的Young氏矩阵( Young tableau)中，每一行的数据都是从左到右排序的，每一列的数据都是从上到下排序的。Young 氏矩阵中也会存在一些值为-∞的数据项，表示那些不存在的元素。因此，Young 氏矩阵可以用来存储r≤m*n个有限的数。\n",
    "\n",
    "1. 画出一个包含元素为(9，16, 3, 2, 4, 8, 5，14, 12}的 4X4Young氏矩阵。\n",
    "2. 对于-一个mXn的Young氏矩阵Y来说，请证明:如果Y[1，1]=∞，则Y为空;如果Y[m，n]<∞,则Y为满(即包含mn个元素)。\n",
    "3. 请给出一个在mXn Young氏矩阵上时间复杂度为O(m+n)的EXTRACT-MIN的算法实现。你的算法可以考虑使用--个递归过程，它可以把-一个规模为mXn的问题分解为规模为(m-1)Xn或者mX(n- 1)的子问题(提示:考虑使用MAX HEAPIFY)。这里，定义T(p)用来表示EXTRACT-MIN在任- - mXn的Young氏矩阵上的时间复杂度，其中p=m十n。给出并求解T(p)的递归表达式，其结果为O(m+n)。\n",
    "4. 试说明如何在O(m+n)时间内，将-一个新元素插入到一个未满的mXn的Young氏矩阵中。\n",
    "5. 在不用其他排序算法的情况下，试说明如何利用-个nXn的Young氏矩阵在O(n2 )时间内将n2个数进行排序。\n",
    "6.设计一个时间复杂度为O(m+n)的算法，它可以用来判断-一个给定的数是否存储在mXn\n",
    "的Young氏矩阵中。\n"
   ],
   "id": "ddd141acf6d39e93"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class YoungMatrix:\n",
    "    \"\"\"\n",
    "    最小值在矩阵的（0，0）处，行数越大，则放入该行最大处的值越大\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, m: int, n: int):\n",
    "        self.matrix: List[List[T]] = [[None] * n for i in range(m)]\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.length = 0\n",
    "\n",
    "    def ExtractMin(self) -> T:\n",
    "        Min = self.matrix[0][0]\n",
    "        self.__MinHeapify(0, 0)\n",
    "        return Min\n",
    "\n",
    "    def AddNewItem(self, item: T) -> None:\n",
    "        i = self.m\n",
    "        j = self.n\n",
    "        Mini = i\n",
    "        Minj = j\n",
    "        Max = item\n",
    "        self.matrix[i][j] = item\n",
    "        while T:\n",
    "            if i > 0 and (self.matrix[i - 1][j] is None or Max < self.matrix[i - 1][j]):\n",
    "                Mini = Mini - 1\n",
    "            if j > 0 and (self.matrix[i][j - 1] is None or Max < self.matrix[i][j - 1]):\n",
    "                Minj = Minj - 1\n",
    "            if self.matrix[i][j] is not None and Max == self.matrix[i][j]:\n",
    "                break\n",
    "            self.matrix[i][j], self.matrix[Mini][Minj] = self.matrix[Mini][Minj], self.matrix[i][j]\n",
    "            j = Minj\n",
    "            i = Mini\n",
    "            Max = self.matrix[i][j]\n",
    "\n",
    "    def FindMax(self) -> tuple[int, int]:\n",
    "        i = self.m\n",
    "        j = self.n\n",
    "        while self.matrix[i][0] is None:\n",
    "            i -= 1\n",
    "        while self.matrix[i][j] is None:\n",
    "            j -= 1\n",
    "        return i, j\n",
    "\n",
    "    def __MinHeapify(self, i: int, j: int) -> None:\n",
    "        \"\"\"\n",
    "        从当前点向左边和下边找到最小值并赋值给当前点，并递归最小值所在的点\n",
    "        \"\"\"\n",
    "        Min = None\n",
    "        Mini = i\n",
    "        Minj = j\n",
    "        if self.matrix[i][j + 1] is not None:\n",
    "            Min = self.matrix[i][j + 1]\n",
    "            Mini = i\n",
    "            Minj = j + 1\n",
    "        if self.matrix[i + 1][j] is not None:\n",
    "            if Min is not None:\n",
    "                if Min < self.matrix[i + 1][j]:\n",
    "                    Min = self.matrix[i + 1][j]\n",
    "                else:\n",
    "                    Mini = i + 1\n",
    "                    Minj = j\n",
    "            else:\n",
    "                Min = self.matrix[i + 1][j]\n",
    "                Mini = i + 1\n",
    "                Minj = j\n",
    "        self.matrix[i][j] = Min\n",
    "        if Mini is not i and Minj is not j:\n",
    "            self.matrix[Mini][Minj] = None\n",
    "            self.__MinHeapify(Mini, Mini)\n"
   ],
   "id": "e6384c0fc2c4d902"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-05T15:20:10.524843Z",
     "start_time": "2024-05-05T15:20:10.520405Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "79bf21c162ab0612",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 None\n"
     ]
    }
   ],
   "execution_count": 190
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
